package dynamic.dpPack;

import java.util.Arrays;

/**
 * 01背包
 */
public class ZeroOnePack {

    // 最大价值 01背包
    private int pack01Dp(int V, int[] c, int[] w) {
        int[][] dp = new int[c.length+1][V+1];
        for (int i=1; i<=c.length; i++) {
            for (int j=1; j<=V; j++) {
                if (j - c[i-1] >= 0) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-c[i-1]]+w[i-1]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
            System.out.println(Arrays.toString(dp[i]));
        }
        return dp[c.length][V];
    }
    // 01背包优化
    private int pack01DpOpt(int V, int[] c, int[] w) {
        int[] dp = new int[V+1];
        for (int i=1; i<=c.length; i++) {
            // 明确每个物体只能使用一次
            // 由上一行数据推测下一行数据，而不是本行推测本行
            //   （倒序 因为上一行数据没有包含本物体）
            // 如果正序， 一个物体可能会被多次计算
            for (int j=V; j>=c[i-1]; j--) { //---------------------倒序，上一行数据不包含本物体
                /**
                 * int[] c = new int[]{2, 3, 4, 5, 1};  // 费用/重量
                 * int[] w = new int[]{6, 5, 4, 3, 2};  // 价值
                 */
                dp[j] = Math.max(dp[j], dp[j-c[i-1]]+w[i-1]);
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[V]; //-------------------------
    }

    private int pack01DpOpt1(int V, int[] c, int[] w) {
        int[] dp = new int[V+1];
        for (int i=1; i<=c.length; i++) {
            zeroOnePack(dp, V, c[i-1], w[i-1]);
            System.out.println(Arrays.toString(dp));
        }
        return dp[V];
    }

    public int zeroOnePack(int[] F, int V, int C, int W) {
        for (int j=V; j>=C; j--) {
            F[j] = Math.max(F[j], F[j-C]+W);
        }
        return F[V];
    }


    public static void main(String[] args) {
        int[] c = new int[]{2, 3, 4, 5, 1};  // 费用/重量
        int[] w = new int[]{6, 5, 4, 3, 2};  // 价值
        int V = 4;  // 背包容量
        ZeroOnePack zeroOnePack = new ZeroOnePack();
        int ans1 = zeroOnePack.pack01Dp(V, c, w);
        System.out.println("dp:"+ans1);

        int ans2 = zeroOnePack.pack01DpOpt(V, c, w);
        System.out.println("dp opt:"+ans2);

        int ans3 = zeroOnePack.pack01DpOpt1(V, c, w);
        System.out.println("dp opt1:"+ans3);
    }
}
